package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202411;

public class leetcode20241120 {
    /**
     * 新增道路查询后的最短距离II：区间并查集
     * @param n
     * @param queries
     * @return
     */
    public int[] shortestDistanceAfterQueries(int n,int[][] queries){
        UnionFind uf=new UnionFind(n-1);
        int[] ans=new int[queries.length];
        int cnt=n-1;
        for(int qi=0;qi<queries.length;qi++){
            int l=queries[qi][0];
            int r=queries[qi][1]-1;
            int fr=uf.find(r);
            for(int i=uf.find(l);i<r;i=uf.find(i+1)){
                uf.fa[i]=fr;
                cnt--;
            }
            ans[qi]=cnt;
        }
        return ans;
    }

    public static void main(String[] args){
        leetcode20241120 leetcode20241120=new leetcode20241120();
        int n=5;
        int[][] queries={{2,4},{0,2},{0,4}};
        int[] ans=leetcode20241120.shortestDistanceAfterQueries(n,queries);
        for(int num : ans){
            System.out.print(num+" ");
        }
        System.out.println();
    }
}

class UnionFind{
    public final int[] fa;

    public UnionFind(int size){
        fa=new int[size];
        for(int i=1;i<size;i++){
            fa[i]=i;
        }
    }

    public int find(int x){
        if(fa[x]!=x){
            fa[x]=find(fa[x]);
        }
        return fa[x];
    }
}
